<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>算法复习总结 | Gip</title>
    <meta name="generator" content="VuePress 1.7.1">
    <link rel="icon" href="/blog/favicon.ico">
    <meta name="description" content="VuePress搭建">
    <meta name="viewport" content="width=device-width,initial-scale=1,user-scalable=no">
    
    <link rel="preload" href="/blog/assets/css/0.styles.41872836.css" as="style"><link rel="preload" href="/blog/assets/js/app.ce46b86f.js" as="script"><link rel="preload" href="/blog/assets/js/2.262e1e49.js" as="script"><link rel="preload" href="/blog/assets/js/13.09133bea.js" as="script"><link rel="prefetch" href="/blog/assets/js/10.8f2ab6cd.js"><link rel="prefetch" href="/blog/assets/js/11.0e5fc533.js"><link rel="prefetch" href="/blog/assets/js/12.61fc7a48.js"><link rel="prefetch" href="/blog/assets/js/14.310e3a44.js"><link rel="prefetch" href="/blog/assets/js/15.d17fc55a.js"><link rel="prefetch" href="/blog/assets/js/16.4550e420.js"><link rel="prefetch" href="/blog/assets/js/17.ceff577e.js"><link rel="prefetch" href="/blog/assets/js/18.b6b9ff56.js"><link rel="prefetch" href="/blog/assets/js/3.115df618.js"><link rel="prefetch" href="/blog/assets/js/4.5b96068b.js"><link rel="prefetch" href="/blog/assets/js/5.7e3d77e5.js"><link rel="prefetch" href="/blog/assets/js/6.0175cad5.js"><link rel="prefetch" href="/blog/assets/js/7.861de91f.js"><link rel="prefetch" href="/blog/assets/js/8.db580af8.js"><link rel="prefetch" href="/blog/assets/js/9.60e428ab.js">
    <link rel="stylesheet" href="/blog/assets/css/0.styles.41872836.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/blog/" class="home-link router-link-active"><img src="/blog/logo.jpg" alt="Gip" class="logo"> <span class="site-name can-hide">Gip</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/blog/" class="nav-link">
  Home
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="Contact" class="dropdown-title"><span class="title">Contact</span> <span class="arrow down"></span></button> <button type="button" aria-label="Contact" class="mobile-dropdown-title"><span class="title">Contact</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="https://github.com/Gip886" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li></ul></div></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"><div class="nav-item"><a href="/blog/" class="nav-link">
  Home
</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="Contact" class="dropdown-title"><span class="title">Contact</span> <span class="arrow down"></span></button> <button type="button" aria-label="Contact" class="mobile-dropdown-title"><span class="title">Contact</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="https://github.com/Gip886" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li></ul></div></div> <!----></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>vue教程</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group depth-0"><p class="sidebar-heading"><span>Web教程</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/blog/views/web/v2.html" class="sidebar-link">本文主要内容</a></li><li><a href="/blog/views/web/v3.html" class="sidebar-link">Web 存储</a></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>JSP教程</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>软件工程实践</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>算法设计</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/blog/views/suanfa/01.html" aria-current="page" class="active sidebar-link">算法复习总结</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/blog/views/suanfa/01.html#第一章算法复杂性分析" class="sidebar-link">第一章算法复杂性分析</a></li><li class="sidebar-sub-header"><a href="/blog/views/suanfa/01.html#第二章递归与分治策略" class="sidebar-link">第二章递归与分治策略</a></li><li class="sidebar-sub-header"><a href="/blog/views/suanfa/01.html#第三章动态规划" class="sidebar-link">第三章动态规划</a></li><li class="sidebar-sub-header"><a href="/blog/views/suanfa/01.html#第四章贪心算法" class="sidebar-link">第四章贪心算法</a></li><li class="sidebar-sub-header"><a href="/blog/views/suanfa/01.html#第五章回溯法" class="sidebar-link">第五章回溯法</a></li><li class="sidebar-sub-header"><a href="/blog/views/suanfa/01.html#附" class="sidebar-link">附</a></li><li class="sidebar-sub-header"><a href="/blog/views/suanfa/01.html#动态规划算法与贪心算法的异同" class="sidebar-link">动态规划算法与贪心算法的异同:</a></li></ul></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>Spring学习</span> <span class="arrow right"></span></p> <!----></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="算法复习总结"><a href="#算法复习总结" class="header-anchor">#</a> 算法复习总结</h1> <h2 id="第一章算法复杂性分析"><a href="#第一章算法复杂性分析" class="header-anchor">#</a> 第一章算法复杂性分析</h2> <blockquote><p>时间复杂性T(n)</p> <p>空间复杂性S(n)</p> <p>(其中n是问题的规模)</p></blockquote> <p>1)渐进上界符号O</p> <blockquote><p>O(g(n))={f(n)|存在正常数C和n0使得对所有n&gt;=n0有：</p> <p>0&lt;=f(n)&lt;=cg(n)}</p> <p>则O(g(n))是f(n)的上界</p> <p>f(n)=O(g(n))</p></blockquote> <p>2)渐进下界符号Ω</p> <blockquote><p>Ω(g(n))={f(n)|存在正常数C和n0使得对所有n&gt;=n0有：</p> <p>0&lt;=cg(n)&lt;=f(n)}</p> <p>则Ω(g(n))是f(n)的下界</p> <p>f(n)=Ω(g(n))</p></blockquote> <p>3)同阶符号Θ s</p> <blockquote><p>Θ(g(n))={f(n)|存在正常数C1，C2和n0使得对所有n&gt;=n0有：</p> <p>c1g(n)&lt;=f(n)&lt;=c2g(n)}</p> <p>f(n)=Θ(g(n))</p></blockquote> <p>填空题：</p> <p>算法性质包括：</p> <ol><li>输入</li> <li>输出</li> <li>确定性</li> <li>有限性</li></ol> <p>算法的复杂性是<strong>算法效率</strong>的度量，是评价算法优劣的重要依据</p> <p>计算机的最重要的是<strong>时间</strong>和<strong>空间</strong>资源，算法复杂性分为<strong>时间复杂度</strong>和<strong>空间复杂度</strong></p> <p>递归是指函数<strong>直接</strong>或者<strong>间接</strong>通过一些语句调用自己</p> <p><img src="https://raw.githubusercontent.com/Gip886/picture/master/img/20210111162738.png" alt="image-20210111162737001"></p> <p>独立</p> <p><img src="https://raw.githubusercontent.com/Gip886/picture/master/img/20210111163348.png" alt="image-20210111163311690"><img src="https://raw.githubusercontent.com/Gip886/picture/master/img/20210111163417.png" alt="image-20210111163416692"></p> <p><img src="https://raw.githubusercontent.com/Gip886/picture/master/img/20210111163509.png" alt="image-20210111163505419"></p> <h2 id="第二章递归与分治策略"><a href="#第二章递归与分治策略" class="header-anchor">#</a> 第二章递归与分治策略</h2> <p>分治法基本思想：</p> <ol><li>将一个规模为n的问题分解成k个规模较小的子问题</li> <li>这些子问题互相独立且与原问题相同</li> <li>递归地解决这些子问题，然后将各个子问题的解合并得到原问题的解</li></ol> <p>递归的概念：<strong>直接</strong>或<strong>间接</strong>地<strong>调用自身</strong>的算法称为<strong>递归算法</strong>，用函数自身给出定义的函数称为递归函数。每个递归函数都要有<strong>非递归定义的初始值</strong>，如阶乘函数，斐波那契，汉诺塔。</p> <p>汉诺塔问题（背）</p> <p>次数：
$$
2^n-1
$$</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>public static hanoi (int n , int a , int b,int c){
	if(n&gt;0){
		hanoi(n-1,a,c,b);
		move(a,b),
		hanoi(n-1,c,b,a);//剩下n-1个c移到b借助a
	}
} 
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br></div></div><p>二分搜索技术（背）</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>public static binarySearch(int [] a, int x, int n){
	int left=0;
	int right=n-1;
	while(left&lt;=right){
		int middle=(left+right)/2;
		if(x==a[middle])return middle;
		if(x&gt;a[middle])left=middle+1;
		else right=middle-1;
	}
	return -1;//未找到下标
}
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br></div></div><p>快速排序问题</p> <p>算法：</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>private static void qSort(int p , int r){
	if(p&lt;r){
		int q = partition(p,r)//找基准元素
		qSort(p,q-1);//对左半段排序 
		qSort(q+1,r); //对右半段排序 
	}
}
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br></div></div><p>找基准元素算法</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>provate static int partition(int p,int r){
	int i = p,//左边的游标，自左向右找比轴大的元素
	j = r+1;//右边的游标，自右向左找比轴小的元素
	Comparable x = a[p];//用最左边的元素作为轴
	//将&lt;x的元素交换到左边区域
	//将&gt;x的元素交换到右边区域
	while(true){
		while(a[++i].compareTo(x)&lt;0&amp;&amp;i&lt;r);
		while(a[--j].compareTo(x)&gt;0);
		if(i&gt;=j)break;
		MyMath.swap(a,i,j);
	} 
	a[p]=a[j];
	a[j]=x;
	return j;
}
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br></div></div><p><strong>俩游标分别从子数组的首尾元素开始向中间移动，i的作用是寻找比轴大的元素，然后让其与j替换，j的作用是寻找比轴小的元素，让其与i替换。</strong></p> <p>全排列问题：</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>public static void perm (Object [] list , int k , int m){
	//产生list[k:m]的所有排列
	if(k==m){
		//只剩下一个元素
		for(int i=0;i&lt;=m;i++){
			System.out.print(list[i]);
			
		}
		System.out.println();
	} 
	else
	//还有很多元素，递归产生排列 
		for(int i =k;i&lt;=m;i++){
			MyMath.swap(list,k,i);
			perm(list,k+1,m);
			MyMath.swap(list,k,i);
		} 
}
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br></div></div><h2 id="第三章动态规划"><a href="#第三章动态规划" class="header-anchor">#</a> 第三章动态规划</h2> <p>基本思想：</p> <p><strong>和分治法类似，都是将待求问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。而动态规划的子问题往往是相互不独立的，所以可以用一个表来记录所有子问题的解，以免再之后重复计算。</strong></p> <p>也是将待求解问题分解成若干个子问题，先求子问题，然后从这些子问题的解得到原问题的解</p> <p>不同之处在于：用一个表来记录所有解决的子问题的解</p> <p><strong>动态规划基本要素：</strong></p> <p><strong>「1」最优子结构性质：</strong></p> <ul><li>当问题的最优解包含了其子问题的最优解时，则称该问题具有最优子结构性质。这个性质是动态规划算法求解的重要线索。</li></ul> <p><strong>「2」子问题重叠性质</strong></p> <ul><li>在运用递归算法自顶向下解题时，每次产生的子问题并不总是新问题，动态规划将计算过的子问题保存在一个表格中，当再次使用时直接搜索到它拿过来用就行了。</li></ul> <p>通常按以下步骤设计动态规划算法</p> <ol><li>找出最优解的性质，并刻画其结构特征</li> <li>递归地定义最优值</li> <li>以自底向上的方式计算出最优值</li> <li>根据计算最优值时得到的信息，构造最优解</li></ol> <p>矩阵连乘公式：</p> <p><img src="https://raw.githubusercontent.com/Gip886/picture/master/img/20210111155245.png" alt="img"></p> <p><strong>每计算出一个C的元素，需要做n次乘法和n-1次加法，n^2个元素时间为O(n^3)；</strong></p> <blockquote><p>找出一种最优的乘法次序</p> <p>普通算法是，A矩阵的第i行各个元素与B矩阵的第i列的各个元素相乘求和，用动态规划，我们可以先假设在第k位置上将矩阵链断开，找到最优解，则问题变成了两个子问题：（AiAi+1……Ak），（Ak+1……Aj）</p> <p>用m[i][j]表示矩阵i到矩阵j连乘的最优值，那么两个子问题对应的最优值变成m[i][k],m[k+1][j]，把这两个加起来，再加上这两大块矩阵（A[i,k]和A[k+1,j]）相乘的计算量，即为A[i,j]的最优次序。</p> <p>设矩阵Am的行数为pm，列数为qm，矩阵是可连乘的，即相邻矩阵qm=pm，所以（AiAi+1……Ak）可表示为pi * qk，</p> <p>（Ak+1……Aj）可表示为pk* qj，qk = pk.则两个矩阵连乘的乘法次数为Pi * Pk* qj。</p> <p><strong>得到最优值的递推定义：</strong></p> <p><strong>m[i][j]=0,i==j</strong></p> <p><strong>m[i][j]=min(k从i到j-1){m[i][k]+m[k+1][j]+pi-1pkpj}</strong></p> <p><strong>时间复杂度O(n^3)</strong></p></blockquote> <p>最长公共子序列公式：</p> <p><img src="https://raw.githubusercontent.com/Gip886/picture/master/img/20210111155428.jpeg" alt="img"></p> <blockquote><p>X{x1,x2...,xm},Y{y1,y2...,yn},设最长子序列为Z={z1,z2,....,zk}</p> <p>这个问题分三种情况解决，一，当用动态规划解决，若xm=yn,则zk=xm=yn,zk-1是Xm-1和Yn-1的最长子序列；二，当xm!=yn且</p> <p>xm!=zk,则Z是Xm-1和Yn的最长子序列，三，同二，当xm!=yn且ym!=zk,则Z是Xm和Yn-1的最长子序列。这样就满足了最优子结构性质。</p> <p>用C[i][j]来记录Xi,Yj的最优子序列的长度，根据上面三种情况，递推公式很容易出来了，不再赘述。</p></blockquote> <p>全排列问题：</p> <p><img src="https://raw.githubusercontent.com/Gip886/picture/master/img/20210111164846.png" alt="image-20210111164845652"></p> <p><img src="https://raw.githubusercontent.com/Gip886/picture/master/img/20210111164859.png" alt="image-20210111164857837"></p> <p>01背包问题：</p> <p>m(i,j)为背包容量为j,可选物品为i,i+1,i+2,...n时的最优值。对于每一个都有装和不装两种，取两者最大。</p> <p>m(i,j)=max{m(i+1,j),m(i+1,j-wi)+vi} ,j&gt;=wi</p> <p>m(i,j)=m(i+1,j), 0&lt;=j&lt;wi</p> <hr> <p>m(n,j)=vn , j&gt;wn</p> <p>m(n,j)=0 , 0&lt;=j&lt;wn</p> <p>https://blog.csdn.net/qq_38984851/article/details/81133096</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>void Knapsack(int v[],int w[],int c,int n,int m[][10])  
{  
	int n=v.length-1;
    int jMax = min(w[n]-1,c);//背包剩余容量上限 范围[0~w[n]-1]  
    for(int j=0; j&lt;=jMax;j++)  
    {  
        m[n][j]=0;  
    }  
    for(int j=w[n]; j&lt;=c; j++)//限制范围[w[n]~c]  
    {  
        m[n][j] = v[n];  
    }  
    for(int i=n-1; i&gt;1; i--)  
    {  
        jMax = min(w[i]-1,c);  
        for(int j=0; j&lt;=jMax; j++)//背包不同剩余容量j&lt;=jMax&lt;c  
        {  
            m[i][j] = m[i+1][j];//没产生任何效益  
        }  
        for(int j=w[i]; j&lt;=c; j++) //背包不同剩余容量j-wi &gt;c  
        {  
            m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//效益值增长vi   
        }  
    }  
    m[1][c] = m[2][c];  
    if(c&gt;=w[1])  
    {  
        m[1][c] = max(m[1][c],m[2][c-w[1]]+v[1]);  
    }  
}  
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br></div></div><p>m[1,c]即为所求</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>//x[]数组存储对应物品0-1向量,0不装入背包，1表示装入背包  
void Traceback(int m[][10],int w[],int c,int n,int x[])  
{  
    for(int i=1; i&lt;n; i++)  
    {  
        if(m[i][c] == m[i+1][c])  
        {  
            x[i]=0;  
        }  
        else  
        {  
            x[i]=1;  
            c-=w[i];  
        }  
    }  
    x[n]=(m[n][c])?1:0;  
}   
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br></div></div><p>活动安排：</p> <div class="language- line-numbers-mode"><pre class="language-text"><code> public static greedySelector(int [] s,int[] f, boolean[] a){
 	int n=s.length-1;
 	a[1]=true;
 	int j = 1;
 	int count = 1;
 	for(int i =2;i&lt;=n;i++){
 		if(s[i]&gt;=f[j]){
 			a[i]=true;
 			j=i;
 			count++;
		 }
		 else a[i=false;]
	 }
	 return count;
 } 
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br></div></div><h2 id="第四章贪心算法"><a href="#第四章贪心算法" class="header-anchor">#</a> 第四章贪心算法</h2> <blockquote><p><strong>贪心算法并不从整体的最优解考虑，而是做出当前的局部最优的选择。两个要素是组优子结构和贪心选择性质，贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择(即贪心选 择)来达到。</strong></p></blockquote> <p>基本思想：</p> <p>贪心算法总是做出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所做的选择只能是在某种意义上的局部最优选择。</p> <p>使用贪心算法解决问题，问题必须具有两个性质：</p> <ol><li><strong>贪心选择性质</strong></li> <li><strong>最优子结构性质</strong></li></ol> <p>贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。</p> <p>最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称问题具有最优子结构性质。</p> <p>01背包和背包问题都具有最优子结构性质，但是背包问题才可以用贪心算法来解决。</p> <p>背包问题贪心算法代码：</p> <p>最优装载：</p> <div class="language- line-numbers-mode"><pre class="language-text"><code>public static float loading(float c,float[] w,int [] x){
	int n = w.length;
	Element []d=new Element[n];
	for(int i = 0 ;i&lt; n;i++){
		d[i]=new Element(w[i],i);
	}
	MergeSort.mergeSort(d);
	float opt= 0;
	for(int i=0;i&lt;n;i++)x[i]=0;
	for(int i =0;i&lt;n&amp;&amp;d[i].w&lt;=c;i++){
		x[d[i].i]=1;
		opt+=d[i].w;
		c-=d[i].w;
	}
	return opt;
}
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br></div></div><p>prim算法：普利姆算法</p> <p><img src="https://raw.githubusercontent.com/Gip886/picture/master/img/20210111164414.png" alt="image-20210111164413235"></p> <p>Kruskal算法：</p> <p>所以克鲁斯卡尔算法的具体思路是：</p> <blockquote><p>将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。</p></blockquote> <p><strong>Prim算法（保证连通，加n-1条边）：时间复杂度O(n^2)</strong></p> <p><strong>Kruskal算法（保证无回路，加n-1条边）：时间复杂度：O(nlogn)</strong></p> <h2 id="第五章回溯法"><a href="#第五章回溯法" class="header-anchor">#</a> 第五章回溯法</h2> <blockquote><p>回溯法的基本思想是:</p> <p>为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。</p></blockquote> <p>以深度优先的方式系统搜索问题解的算法称为回溯法</p> <p>基本思想：</p> <p><img src="https://raw.githubusercontent.com/Gip886/picture/master/img/20210111163714.png" alt="image-20210111163713762"></p> <p>以深度优先的方式在解空间递归地寻找解，直到找到问题地解或者解空间已无活动节点为止</p> <blockquote><p><strong>回溯法的两种解空间树:子集树和排列树;</strong></p> <p>剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。</p> <p><strong>如背包是子集树，售货商是排列树(O(n!))</strong></p></blockquote> <h2 id="附"><a href="#附" class="header-anchor">#</a> 附</h2> <p><img src="https://raw.githubusercontent.com/Gip886/picture/master/img/20210111163848.png" alt="image-20210111163847626"></p> <p>简单说p等于易问题，</p> <p>np等于难问题</p> <h2 id="动态规划算法与贪心算法的异同"><a href="#动态规划算法与贪心算法的异同" class="header-anchor">#</a> 动态规划算法与贪心算法的异同:</h2> <blockquote><p><strong>共同点：</strong></p> <p><strong>都需要最优子结构性质</strong>，</p> <p>​       都用来求有优化问题。</p> <p><strong>不同点：</strong></p> <p><strong>动态规划</strong>：每一步作一个选择——<strong>依赖于子问题的解</strong>。</p> <p>​      <strong>贪心方法</strong>：每一步作一个选择——<strong>不依赖于子问题的解</strong>。</p> <p>​      <strong>动态规划方法的条件：最优子结构性质；子问题的重叠性质。</strong></p> <p>​      <strong>可用贪心方法的条件：最优子结构性质；贪心选择性质。</strong></p> <p>动态规划：<strong>自底向上求解</strong>（动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构）</p> <p>​       贪心方法： <strong>自顶向下求解</strong>。</p> <p>​		可用贪心法时，动态规划方法可能不适用；</p> <p>​        可用动态规划方法时，贪心法可能不适用。</p></blockquote></div> <footer class="page-edit"><!----> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
      ←
      <a href="/blog/views/software/01.html" class="prev">
        软件工程实践复习
      </a></span> <span class="next"><a href="/blog/views/Spring/01.html">
        Spring学习（1）
      </a>
      →
    </span></p></div> </main></div><div class="global-ui"></div></div>
    <script src="/blog/assets/js/app.ce46b86f.js" defer></script><script src="/blog/assets/js/2.262e1e49.js" defer></script><script src="/blog/assets/js/13.09133bea.js" defer></script>
  </body>
</html>
